package com.fc.primary.sort;

import java.util.Random;

/**
 * @program: fc-java->Fs
 * @description:
 * @author: G_Y
 * @create: 2019-09-02 15:04
 **/
public class Fs {
    private static int[] arr = new int[50];
    private static int len = arr.length;

    static {
        Random r = new Random();
        for (int i = 0; i < 50; i++) {
            arr[i] = r.nextInt(100);
        }
        p();
    }

    public static void main(String[] args) {
        fast(0, len - 1);
        System.out.println("");
        p();
    }

    public static int f(int left, int right) {
        // 挖坑填数
        int x = arr[left];
        // 直至两个指针相碰
        while (left < right) {
            // 先从右至左找一个比x小的数
            while (arr[right] >= x && left < right) {
                right--;
            }
            // 找到右边小的数,把它放到左边的坑，然后右边出现坑
            if (left < right) {
                arr[left++] = arr[right];
            }
            // 再从左至右找一个比x大的数
            while (arr[left] <= x && left < right) {
                left++;
            }
            // 找到左边大的数，把它放到右边刚刚产生的坑，然后左边又产生坑，循环
            if (left < right) {
                arr[right--] = arr[left];
            }
        }
        // 那么则将最先挖出的那个x值填在最后一个坑处
        // 保证 经过此次排序之后，x的左边都是比x小的数，x的右边都是比它大的数
        arr[left] = x;
        return left;
    }

    public static void fast(int left, int right) {
        if (right <= left) {
            return;
        }
        int mind = f(left, right);
        // 一次排序后，数组下标mind处值则确定，将数组拆成两部分继续排序
        fast(left, mind - 1);
        fast(mind + 1, right);

    }


    public static void p() {
        for (int a : arr) {
            System.out.print(a + " ");
        }
    }
}
